GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Μ-Rekursion</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">μ-Rekursion</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der <a href="Rekursionstheorie" class="mw-redirect" title="Rekursionstheorie">Rekursionstheorie</a>, einem Teilgebiet der <a href="Theoretische_Informatik" title="Theoretische Informatik">theoretischen Informatik</a>, eine wichtige Rolle (µ für <a href="Neugriechische_Sprache" title="Neugriechische Sprache">griechisch</a> μικρότατος ‚das kleinste‘). Nach der <a href="Church-Turing-These" title="Church-Turing-These">Church-Turing-These</a> beschreibt sie die Menge aller Funktionen, die im intuitiven Sinn <a href="Berechenbarkeit" title="Berechenbarkeit">berechenbar</a> sind. Eine wichtige echte <a href="Teilmenge" title="Teilmenge">Teilmenge</a> der μ-rekursiven Funktionen sind die <a href="Primitiv-rekursive_Funktion" title="Primitiv-rekursive Funktion">primitiv-rekursiven Funktionen</a>.

Die Klasse der μ-rekursiven Funktionen stimmt überein mit der Klasse der <a href="Turing-Berechenbarkeit" class="mw-redirect" title="Turing-Berechenbarkeit">Turing-berechenbaren</a> Funktionen sowie weiteren gleich mächtigen Berechenbarkeitsmodellen, wie dem <a href="Lambda-Kalk%C3%BCl" title="Lambda-Kalkül">Lambda-Kalkül</a>, <a href="Registermaschine" title="Registermaschine">Registermaschinen</a> und <a href="WHILE-Programm" title="WHILE-Programm">WHILE-Programmen</a>.

Die primitiv-rekursiven Funktionen sind aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgerfunktion) durch Komposition und primitive Rekursion aufgebaut. Dadurch erhält man immer totale Funktionen, also Funktionen im eigentlichen Sinn.

Die μ-rekursiven Funktionen sind demgegenüber <a href="Partielle_Funktion" title="Partielle Funktion">partielle Funktionen</a>, die aus denselben Konstrukten und zusätzlich durch die Anwendung des μ-Operators gebildet werden können. Durch die Anwendung des μ-Operators wird Partialität eingeführt. Jedoch ist nicht jede μ-rekursive Funktion nicht-total. Beispielsweise sind alle primitiv-rekursiven Funktionen auch μ-rekursiv. Ein Beispiel für eine nicht primitiv-rekursive, totale, μ-rekursive Funktion ist die <a href="Ackermannfunktion" title="Ackermannfunktion">Ackermannfunktion</a>.

<div class="mw-heading mw-heading2"><h2 id="Definition_des_μ-Operators">Definition des μ-Operators</h2></div>

Für eine partielle Funktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\colon \mathbb {N} ^{k+1}\to \mathbb {N} }">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\colon \mathbb {N} ^{k+1}\to \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/36388a0cd357ad93dd60e30f0f91c9de0516c93c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.472ex; height:3.009ex;" alt="{\displaystyle f\colon \mathbb {N} ^{k+1}\to \mathbb {N} }" loading="lazy"> und natürliche Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1};\dots ;x_{k}\in \mathbb {N} }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1};\dots ;x_{k}\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b36b2ea556c978255e9a56016c718736c51a3e6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.499ex; height:2.509ex;" alt="{\displaystyle x_{1};\dots ;x_{k}\in \mathbb {N} }" loading="lazy"> sei die Menge

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(f,x_{1},\dots ,x_{k})=\{n\in \mathbb {N} \mid f(x_{1},\dots ,x_{k},n)=0\ \land \ \forall 0\leq m\leq n\colon f(x_{1},\dots ,x_{k},m)\downarrow \}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53c14893725fcb1d885bcd328d4e175270ce6fc1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:84.392ex; height:2.843ex;" alt="{\displaystyle M(f,x_{1},\dots ,x_{k})=\{n\in \mathbb {N} \mid f(x_{1},\dots ,x_{k},n)=0\ \land \ \forall 0\leq m\leq n\colon f(x_{1},\dots ,x_{k},m)\downarrow \}}" loading="lazy"></dd></dl>

festgehalten, also die Gesamtheit aller <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> derart, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> an der Stelle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},\dots ,x_{k},n)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1},\dots ,x_{k},n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eb55ee4f9718b272cd95aab8c24806fa3f403823.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.218ex; height:2.843ex;" alt="{\displaystyle (x_{1},\dots ,x_{k},n)}" loading="lazy"> identisch 0 verschwindet und zusätzlich für alle Punkte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},\dots ,x_{k},m)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1},\dots ,x_{k},m)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5b85420867d379a102ad7ec4eadd1974d8372a44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.864ex; height:2.843ex;" alt="{\displaystyle (x_{1},\dots ,x_{k},m)}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\leq n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\leq n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0017737947454c2911336b2d038c91f5a7a70bc0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.534ex; height:2.176ex;" alt="{\displaystyle m\leq n}" loading="lazy"> definiert ist.

Zu beachten ist dabei, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M(f,x_{1},\dots ,x_{k})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(f,x_{1},\dots ,x_{k})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a50c7259956c2090a342cba44fb9080274785e63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.545ex; height:2.843ex;" alt="{\displaystyle M(f,x_{1},\dots ,x_{k})}" loading="lazy"> als Menge <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlicher Zahlen</a> genau dann ein <a href="Gr%C3%B6%C3%9Ftes_und_kleinstes_Element" title="Größtes und kleinstes Element">Minimum</a> besitzt, wenn sie nicht leer ist (vgl. <a href="Wohlordnung" title="Wohlordnung">Wohlordnung</a>).

Durch Anwendung des <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy">-Operators auf <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> entstehe nun die partielle Funktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu f\colon \mathbb {N} ^{k}\to \mathbb {N} }">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu f\colon \mathbb {N} ^{k}\to \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/70f71ea173468ae01b275bb5302ab26eeb131e99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.773ex; height:3.176ex;" alt="{\displaystyle \mu f\colon \mathbb {N} ^{k}\to \mathbb {N} }" loading="lazy">, definiert durch:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mtext>falls </mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>undefiniert</mtext>

</mrow>

</mtd>

<mtd>

<mtext>sonst</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu f(x_{1},\dots ,x_{k})={\begin{cases}\min M(f,x_{1},\dots ,x_{k}),&{\text{falls }}M(f,x_{1},\dots ,x_{k})\neq \emptyset \\{\text{undefiniert}}&{\text{sonst}}\end{cases}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf552713873bf03f1c15f31a2895f1bd810589c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:69.31ex; height:6.176ex;" alt="{\displaystyle \mu f(x_{1},\dots ,x_{k})={\begin{cases}\min M(f,x_{1},\dots ,x_{k}),&{\text{falls }}M(f,x_{1},\dots ,x_{k})\neq \emptyset \\{\text{undefiniert}}&{\text{sonst}}\end{cases}}}" loading="lazy"></dd></dl>

Insbesondere bildet der Operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> also eine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (k+1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (k+1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3f9f13644a6be482d7ddb19a6e0c706564773085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.023ex; height:2.843ex;" alt="{\displaystyle (k+1)}" loading="lazy">-stellige partielle Funktion auf eine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-stellige partielle Funktion ab.

Für berechenbares <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> kann das Programm zur Berechnung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c99072e42c281e3f5b8bf04fb17226aa42d331cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.68ex; height:2.676ex;" alt="{\displaystyle \mu f}" loading="lazy"> verstanden werden als eine <a href="While-Schleife" class="mw-redirect" title="While-Schleife">While-Schleife</a>, die nach oben zählt und die deswegen nicht <a href="Terminiertheit" title="Terminiertheit">terminieren</a> muss:

Parameter: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},\ldots ,x_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1},\ldots ,x_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/00a6511886c686290cc57b23ab22f45fda9e1c12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.981ex; height:2.009ex;" alt="{\displaystyle x_{1},\ldots ,x_{k}}" loading="lazy">.

Setze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> auf <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy">;

Solange <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x_{1},\dots ,x_{k},n)\neq 0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x_{1},\dots ,x_{k},n)\neq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d4098d71c3df3423abbd3747901a2477746560ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.758ex; height:2.843ex;" alt="{\displaystyle f(x_{1},\dots ,x_{k},n)\neq 0}" loading="lazy">, erhöhe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> um <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">;

Ergebnis: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.

</div>

<div class="mw-heading mw-heading2"><h2 id="Definition_der_μ-rekursiven_Funktionen">Definition der μ-rekursiven Funktionen</h2></div>

Die Klasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Pr}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Pr}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7682249689adb4cb4ebf84b74a6f3afe0dd4a825.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.794ex; height:2.176ex;" alt="{\displaystyle Pr}" loading="lazy"> der μ-rekursiven Funktionen (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} ^{k}\to \mathbb {N} }">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} ^{k}\to \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9bf32c33ada6cc27f55f7177ba4be76e12842ca4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.059ex; height:2.676ex;" alt="{\displaystyle \mathbb {N} ^{k}\to \mathbb {N} }" loading="lazy">) umfasst die folgenden Grundfunktionen:

<ol><li>konstante 0-Funktion: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f^{k}\left(n_{1},\dots ,n_{k}\right):=0}">

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{k}\left(n_{1},\dots ,n_{k}\right):=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/42f82478bca7fc6e13ca305e1d027b127eba869a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.624ex; height:3.176ex;" alt="{\displaystyle f^{k}\left(n_{1},\dots ,n_{k}\right):=0}" loading="lazy"></li>

<li>Projektion auf ein Argument: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi _{i}^{k}\left(n_{1},\dots ,n_{k}\right):=n_{i}}">

</mrow>

</mrow>

</msubsup>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{i}^{k}\left(n_{1},\dots ,n_{k}\right):=n_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0df178a73bae032fe11592f88906048661a0d3ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:20.67ex; height:3.176ex;" alt="{\displaystyle \pi _{i}^{k}\left(n_{1},\dots ,n_{k}\right):=n_{i}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/83de74da899efbafa01ec98ebf478e9ce5679fc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.373ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq k}" loading="lazy"></li>

<li>Nachfolgefunktion: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nu \left(n\right):=n+1}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu \left(n\right):=n+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da03606841260b647e488591ee620a3f3c435912.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.966ex; height:2.843ex;" alt="{\displaystyle \nu \left(n\right):=n+1}" loading="lazy"></li></ol>

Die μ-rekursiven Funktionen erhält man als Abschluss der Grundfunktionen bezüglich der drei folgenden Operationen:

<ol><li>der Komposition: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\left(n_{1},\dots ,n_{k}\right):=g\left(h_{1}\left(n_{1},\dots ,n_{k}\right),\dots ,h_{m}\left(n_{1},\dots ,n_{k}\right)\right)}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\left(n_{1},\dots ,n_{k}\right):=g\left(h_{1}\left(n_{1},\dots ,n_{k}\right),\dots ,h_{m}\left(n_{1},\dots ,n_{k}\right)\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9db0ad29319dccd2dd67ecdb675231ba1d24db81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:56.23ex; height:2.843ex;" alt="{\displaystyle f\left(n_{1},\dots ,n_{k}\right):=g\left(h_{1}\left(n_{1},\dots ,n_{k}\right),\dots ,h_{m}\left(n_{1},\dots ,n_{k}\right)\right)}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g,h_{1},\dots ,h_{m}\in Pr}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g,h_{1},\dots ,h_{m}\in Pr}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e15ea45d35a681e0973fb268231fb5ae60e4a828.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.37ex; height:2.509ex;" alt="{\displaystyle g,h_{1},\dots ,h_{m}\in Pr}" loading="lazy"></li>

<li>der primitiven Rekursion: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\left(0,n_{2},\dots ,n_{k}\right):=g\left(n_{2},\dots ,n_{k}\right)}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\left(0,n_{2},\dots ,n_{k}\right):=g\left(n_{2},\dots ,n_{k}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/35b1c7bfd5757a3c32eefdf11f6530de038bb81b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.95ex; height:2.843ex;" alt="{\displaystyle f\left(0,n_{2},\dots ,n_{k}\right):=g\left(n_{2},\dots ,n_{k}\right)}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\left(n_{1}+1,n_{2},\dots ,n_{k}\right):=h\left(f\left(n_{1},\dots ,n_{k}\right),n_{1},\dots ,n_{k}\right)}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\left(n_{1}+1,n_{2},\dots ,n_{k}\right):=h\left(f\left(n_{1},\dots ,n_{k}\right),n_{1},\dots ,n_{k}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/37c07a26c9df0152f9d95fd579e30b68ff537d8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:53.469ex; height:2.843ex;" alt="{\displaystyle f\left(n_{1}+1,n_{2},\dots ,n_{k}\right):=h\left(f\left(n_{1},\dots ,n_{k}\right),n_{1},\dots ,n_{k}\right)}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h,g\in Pr}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h,g\in Pr}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fd9634a7505dd7861b600d11f640a9fc2082a4ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.124ex; height:2.509ex;" alt="{\displaystyle h,g\in Pr}" loading="lazy"></li>

<li>des μ-Operators.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Äquivalenz_der_μ-rekursiven_Funktionen_mit_der_Turingmaschine">Äquivalenz der μ-rekursiven Funktionen mit der Turingmaschine</h2></div>

Es lässt sich beweisen, dass eine <a href="Turingmaschine" title="Turingmaschine">Turingmaschine</a> (TM) durch μ-rekursive Funktionen simuliert werden kann. Es lässt sich auch beweisen, dass die Menge der μ-rekursiven Funktionen genau der Menge der Turing-berechenbaren Funktionen entspricht.

Beweis-Skizze für die Simulation der TM mit μ-rekursiven Funktionen

Man kann zeigen, dass sich die Konfiguration einer TM durch drei Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> darstellen lässt.

Genau so kann eine Funktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(a,b,c)=y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(a,b,c)=y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92337a85282ce920ac310f6db2f1524fd81eb0d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.704ex; height:2.843ex;" alt="{\displaystyle h(a,b,c)=y}" loading="lazy"> (eine bijektive Abbildung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} ^{3}\to \mathbb {N} }">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} ^{3}\to \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c8d1982046043bf77dcce2abeb4ae1d141c31133.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.024ex; height:2.676ex;" alt="{\displaystyle \mathbb {N} ^{3}\to \mathbb {N} }" loading="lazy">) definiert werden, die eine geeignete Kodierung der TM ist.

Nehmen wir also eine primitiv-rekursive Funktion

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n,x)=y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ae0b3d228dc59ac096db834a7ded0f87b6623ec0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.1ex; height:2.843ex;" alt="{\displaystyle f(n,x)=y}" loading="lazy">,</dd></dl>

die eine geeignete Kodierung der TM liefert für die Eingabe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Berechnungsschritten,

und eine zweite primitiv-rekursive Funktion

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(y)=0\lor g(y)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/63e05dda09de74f32704f412c5a93fbff0e87402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.266ex; height:2.843ex;" alt="{\displaystyle g(y)=0\lor g(y)=1}" loading="lazy">,</dd></dl>

die für eine Kodierung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> als Ergebnis 0 liefert, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> einen Endzustand der TM repräsentiert, und ansonsten 1.

Dann ergibt

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Anzahl} (x)=\mu (g(f(n,x)))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/edf49a93956774640aa62477b5eb158b54f0ca78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.39ex; height:2.843ex;" alt="{\displaystyle \mathrm {Anzahl} (x)=\mu (g(f(n,x)))}" loading="lazy"></dd></dl>

die Anzahl der Schritte, die eine TM zur Berechnung bis zum Ende benötigt. Also bekommen wir mit

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Berechnung} (x)=f(\mathrm {Anzahl} (x),x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/282bb8f3185b778c134b8a917c51e1eab13b786d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.985ex; height:2.843ex;" alt="{\displaystyle \mathrm {Berechnung} (x)=f(\mathrm {Anzahl} (x),x)}" loading="lazy"></dd></dl>

die Berechnung der TM in einem Endzustand bei der Eingabe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">.

</div>

<div class="mw-heading mw-heading2"><h2 id="Bemerkung">Bemerkung</h2></div>

<ul><li>Die Berechenbarkeit einer μ-rekursiven Funktion bezieht sich auf Werte aus ihrem Definitionsbereich. Es existiert kein allgemeines Verfahren, das alle Werte liefert, die nicht zum Definitionsbereich einer μ-rekursiven Funktion gehören.</li>

<li>Der μ-Operator realisiert einen Suchprozess, der genau dann abbricht, wenn der gesuchte Wert existiert.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

<ul><li>Alle primitiv-rekursiven Funktionen sind μ-rekursiv.</li>

<li>Die <a href="Ackermannfunktion" title="Ackermannfunktion">Ackermannfunktion</a> und die <a href="Sudanfunktion" title="Sudanfunktion">Sudanfunktion</a> sind totale μ-rekursive Funktionen, die nicht primitiv-rekursiv sind.</li>

<li>Die Funktion <a href="Flei%C3%9Figer_Biber" title="Fleißiger Biber">Fleißiger Biber</a> (busy beaver) ist nicht μ-rekursiv.</li>

<li>Die Folge der Ziffern der Halte-Wahrscheinlichkeit (<a href="Chaitinsche_Konstante" title="Chaitinsche Konstante">Chaitinsche Konstante</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy">) ist nicht μ-rekursiv. Die Halte-Wahrscheinlichkeit ist definiert durch</li></ul>

</mrow>

</munder>

<msup>

<mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega :=\sum _{p}2^{-\left|p\right|}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a4093c5fb163538500d0baf95566aa48bbd8f296.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:13.58ex; height:5.676ex;" alt="{\displaystyle \Omega :=\sum _{p}2^{-\left|p\right|}}" loading="lazy">,</dd></dl></dd>

<dd>wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> ein haltendes Programm ist und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left|p\right|}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left|p\right|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/99c120b5eecfdfb4729e159e6027dab6e180a4c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.463ex; height:2.843ex;" alt="{\displaystyle \left|p\right|}" loading="lazy"> die Länge des Programms in <a href="Bit" title="Bit">Bit</a> bezeichnet.</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Heinz-Dieter_Ebbinghaus" title="Heinz-Dieter Ebbinghaus">Heinz-Dieter Ebbinghaus</a>, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik (= Spektrum-Hochschultaschenbuch.). 4. Auflage. Spektrum – Akademischer Verlag, Heidelberg u. a. 1996, ISBN 3-8274-0130-5.</li>

<li><a href="Hans_Hermes" title="Hans Hermes">Hans Hermes</a>: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen (= Heidelberger Taschenbücher. 87). 2. Auflage. Springer, Berlin u. a. 1971, ISBN 3-540-05334-4.</li>

<li><a href="Arnold_Oberschelp" title="Arnold Oberschelp">Arnold Oberschelp</a>: Rekursionstheorie. BI-Wissenschaftlicher-Verlag, Mannheim u. a. 1993, ISBN 3-411-16171-X.</li>

<li><a href="Wolfgang_Rautenberg" title="Wolfgang Rautenberg">Wolfgang Rautenberg</a>: <cite style="font-style:italic">Einführung in die Mathematische Logik. Ein Lehrbuch</cite>. 3., überarbeitete Auflage. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:%CE%9C-Rekursion&rft.au=Wolfgang+Rautenberg&rft.btitle=Einf%C3%BChrung+in+die+Mathematische+Logik.+Ein+Lehrbuch&rft.date=2008&rft.edition=3.%2C+%C3%BCberarbeitete&rft.genre=book&rft.isbn=9783834805782&rft.place=Wiesbaden&rft.pub=Vieweg+%2B+Teubner" style="display:none"> </li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-12-01" href="https://de.wikipedia.org/wiki/?title=%CE%9C-Rekursion&oldid=262038432">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>